import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/5 8:53
 * @description 线段树，动态开点
 */
public class Solution2 {
    public static void main(String[] args) {
        MyCalendar myCalendar = new MyCalendar();
        boolean book = myCalendar.book(10, 20);
        System.out.println(book);
        boolean book1 = myCalendar.book(15, 25);
        System.out.println(book1);
        boolean book2 = myCalendar.book(20, 30);
        System.out.println(book2);
    }

    public static class MyCalendar {
        /**
         * 实际判断区间是否存在
         */
        Set<Integer> tree;
        /**
         * 懒加载标记
         */
        Set<Integer> lazy;

        public MyCalendar() {
            tree = new HashSet<>();
            lazy = new HashSet<>();
        }

        public boolean book(int start, int end) {
            if (query(start, end - 1, 0, (int)(1e9), 1)) {
                return false;
            }
            update(start, end - 1, 0, (int)1e9, 1);
            return true;
        }

        public boolean query(int start, int end, int l, int r, int idx) {
            if (start > r || end < l) {
                return false;
            }
            if (lazy.contains(idx)) {
                // 懒加载中存在当前结点，说明重合，查询到区间重合
                return true;
            }
            if (start <= l && r <= end) {
                return tree.contains(idx);
            }else {
                int mid = (l + r) >> 1;
                if (end <= mid) {
                    return query(start, end, l, mid, 2 * idx);
                }else if (start > mid) {
                    return query(start, end, mid + 1, r, 2 * idx + 1);
                }else {
                    return query(start, end, l, mid, 2 * idx) | query(start, end, mid + 1, r, 2 * idx + 1);
                }
            }
        }

        public void update(int start, int end, int l, int r, int idx) {
            if (r < start || end < l) {
                return;
            }
            if (start <= l  && r <= end) {
                tree.add(idx);
                lazy.add(idx);
            }else {
                int mid = (l + r) >> 1;
                update(start, end, l, mid, 2 * idx);
                update(start, end, mid + 1, r, 2 * idx + 1);
                tree.add(idx);
            }
        }
    }

}
